1. Field of the Invention
This invention relates to digital image processing, and more specifically to digital image segmentation methods.
2. Description of the Related Art
The capturing and processing of digital images has applications in many fields, including but not limited to applications in the medical, astronomy, and security fields. Digital images may be captured using a variety of mechanisms. Conventionally, images may be captured in the electromagnetic spectrum, including visible light images, infrared images, X-Ray images, radiotelescope images, radar images such as Doppler Radar images, and so on. Common digital image capturing mechanisms for images in the electromagnetic spectrum include, but are not limited to, digitizing cameras that include EM spectrum-sensitive sensors that directly digitize images in the electromagnetic spectrum and film scanners that digitize conventionally photographed or otherwise captured images from film or from photographs. Note that digital images may be captured as grayscale (“black and white”) images or color images, and that color images may be converted to grayscale images and vice versa. Also note that digital images may be captured for viewing objects and events from the subatomic level in particle accelerators, through the microscopic level, and on up to the level of clusters of deep-space galaxies as captured by the Hubble Space Telescope.
Digital images may be generated by other methods than directly capturing images in the electromagnetic spectrum. For example, in the medical field, non-invasive mechanisms have been developed for viewing the internal organs and other internal structures other than the conventional X-Ray. Examples include Magnetic Resonance Imaging (MRI), computed tomography (CT), positron emission tomography (PET), and ultrasound systems. In these systems, data is captured using some indirect mechanism and converted into “conventional” viewable grayscale or color images. Note that at least some of these mechanisms have found applications in other fields than the medical field, for example, in various engineering fields, for example in examining the structural integrity of metals such as structural steel or airplane parts and, in paleontology, in non-invasively viewing the internal structure of a fossil.
Some image capturing mechanisms, such as MRI, CT, and PET systems, may be able to capture digital image “slices” of an object such as a human body. For example, an MRI system may be used to generate a set of images representing “slices” taken through an portion of the human body containing a particular internal organ or organs or other structure—even the entire body may be so imaged. This set of images may be viewed as a three-dimensional (3-D) rendering of the object. Each individual image may be viewed as a “conventional” two-dimensional (2-D) image, but the set of captured images contains data that represents three-dimensional information, and that may be rendered using various rendering techniques into 3-D representations of a particular object or structure.
FIG. 1 illustrates a two-dimensional (2-D) digital image. A pixel (“picture element”) is the basic element or unit of graphic information in a 2-D digital image. A pixel defines a point in two-dimensional space with an x and y coordinate. FIG. 2 illustrates pixels in 2-D image space. Each cube in FIG. 2 represents one element of graphic information, or pixel. Each pixel may be specified by a coordinate on the x and y axes as (x,y). In 2-D image space, a pixel (not on the edge of the image) may be considered as having eight adjacent pixels, if diagonally-adjacent pixels are considered as connected. For example, pixel (1,1) in FIG. 2 has eight-connected pixels. If diagonally-adjacent pixels are not considered as connected, a non-edge pixel would have only four connected pixels.
In 2-D image space, a region is a connected set of pixels; that is, a set of pixels in which all the pixels are adjacent and connected, and in which the pixels are typically associated according to some other criterion or criteria. In 2-D image space, four-connectivity is when only laterally-adjacent pixels are considered connected; eight-connectivity is when laterally-adjacent and diagonally-adjacent pixels are considered connected.
FIG. 3 illustrates a three-dimensional (3-D) digital image set. A 3-D digital image is essentially a stack or set of 2-D images, with each image representing a “slice” of an object being digitized. A voxel (“volume element”) is an element or unit of graphic information that defines a point in the three-dimensional space of a 3-D digital image. A pixel defines a point in two-dimensional space with an x and y coordinate; a third coordinate (z) is used to define voxels in 3-D space. A voxel may be specified by its coordinates on the three axes, for example as (x,y,z) or as (z,x,y). FIG. 4A illustrates voxels in 3-D image space. Each cube in FIG. 4A represents one element of graphic information, or voxel. Each voxel may be specified by a coordinate on the x, y and z axes as (x,y,z) or (z,x,y). In 3-D image space, a voxel (not on the edge of the image) may be considered as having 26 adjacent voxels, if diagonally-adjacent voxels are considered as connected. For example, voxel (1,1,1) in FIG. 4A has 26 connected voxels. FIG. 4B shows adjacent voxels to voxel (1,1,1) if diagonally-adjacent voxels are not considered as connected. In FIG. 4B, voxel (1,1,1) has six connected voxels.
In 3-D image space, a volume is a connected set of voxels; that is, a set of voxels in which all the voxels are adjacent and connected, and in which the voxels are typically associated according to some other criterion or criteria. In 3-D image space, six-connectivity is when only laterally-located voxels are considered connected; 26-connectivity is when laterally-adjacent and diagonally-adjacent voxels are considered connected.
For simplicity, the term “element” may be used herein to refer to both pixels and voxels. In a digital image, each element (pixel or voxel) may be defined in terms of at least its position and graphic information (e.g., color, and density). The position specifies the location of the element in the 2-D or 3-D image space as coordinates. Color and density are components of the graphic information at the corresponding position. In a color image, the specific color that an element (pixel or voxel) describes is a blend of three components of the color spectrum (e.g., RGB). Note that some graphic information (e.g., color) may not be actually “captured” but instead may be added to an image. For example, an image captured in grayscale may have “pseudocolors” added for various reasons. An example is the various shades of blue, yellow, green and red added to Doppler Radar-captured images to represent various amounts of rainfall over a geographic region.
Image Segmentation
Image segmentation refers to a specific area within digital image processing. Image segmentation is one area within the broader scope of analyzing the content of digital images. Image segmentation may also be viewed as the process of locating and isolating objects within a digital image. Various image segmentation techniques have been developed that may be used in various image processing task such as in locating one or more objects of interest, in separating or segmenting two or more adjacent objects, in finding boundaries of objects, in extracting objects of interest from images, in finding objects or structures within objects, and so on.
Image segmentation techniques generally fall into three different categories that represent three different approaches to the image segmentation problem. In boundary locating techniques, boundaries between regions or volumes are located. In edge detection techniques, edge pixels or voxels of objects or structures within an image are identified and then linked to form boundaries. In region growing techniques, each element or a portion of the elements within an image may be assigned to a particular object, region (for 2-D images), or volume (for 3-D images). Note that, in 3-D image space, “volume growing” is analogous to region growing, although as each image in a set of image constituting a 3-D data set is essentially a 2-D image, region growing techniques may be applied to the individual images or ‘slices’ in the 3-D data set. Further note that region growing techniques developed for 2-D image space can generally be adapted to work in 3-D image space to grow volumes. To avoid confusion herein, the techniques will simply be referred to as “region growing” techniques, although it is important to note that the techniques may be adapted to grow regions in 2-D space or volumes in 3-D space.
As an example of an application of image segmentation techniques, 2-D and 3-D medical images may be segmented for a variety of reasons. For example, in order to measure the volume of a growth or tumor, or to display the coronal tree as a 3D model, sections of 3-D image data captured by MRI, CT Scan, or some other mechanism have to be selected and separated from the entire dataset.
Image segmentation of medical images may be been done manually, and conventionally manual methods have been commonly used. The manual method requires the user to “lasso” the desired pixels in a 2-D image, or voxels in each image in a 3-D data set of two or more captured images or “slices”. Manual image segmentation can be a difficult and time-consuming task, especially in the multi-slice case.
Several automated region growing image segmentation techniques that attempt to grow a region (or volume) from a seed location (indicating a particular pixel or voxel within a desired object) have been developed. Typically, region growing technique start at a seed location and grow the region or volume from there. The seed location may define a graphic value or values that may be used in determining whether connected pixels or voxels will be included in the region or volume being grown. Typically, a tolerance range or threshold(s) is provided to be used in testing graphic components of elements (pixels or voxels) connected to the region or volume being grown to determine if the elements are to be added to the region or volume. Typically, a user selects a seed location as the starting location within an object from which a region (or volume) will be automatically grown according to the particular region growing technique being used, and specifies the tolerance or threshold(s). The seed location specifies a “first element” of the region or volume. One or more graphic components of connected elements to the first element (pixels or voxels) are tested and, if the tested graphic components satisfy the specified threshold(s), the connected elements are added to the region or volume. Connected elements to the region or volume are tested and excluded from or added to the growing region or volume, and so on, until all connected elements have been tested and no more connected elements that satisfy the threshold test can be found. Thus, the region or volume grows until all connected elements (pixels or voxels) that pass the threshold test are found.
Medical images, and some images in other fields, often contain narrow connecting pathways between objects in an image, which may introduce difficulties in segmenting the images. This is particularly problematic in medical imaging as structures like the vascular system are particularly hard to segment as they often contain small connections or pathways to other organs, etc. Region growing techniques that simply look at and test the graphic components of single connected pixels or voxels tend to go down these pathways, and thus may grow regions or volumes well beyond the boundaries of the desired objects.
Some region growing mechanisms that have been developed introduce the concept of a radius around the test location (the current element under test) that is applied in an attempt to prevent growing the region or volume down an undesired narrow connection or path. Instead of testing the graphic components of a single element under test to determine if the element meets the threshold requirements, all of the elements within an area defined by the specified radius are tested. If some specified number, e.g. a majority, 75%, or even all, of the elements within the radius-defined area meet the threshold requirements, then the element is added to the region or volume being grown; otherwise, the element is excluded from the region or volume. By requiring that the test area be larger than a single pixel or voxel, single pixel or voxel connections may be avoided. Increasing the test radius results in a corresponding increased requirement for the size of a connecting pathway, reducing the likelihood that a region or volume will be grown down an undesired path or connection.
A problem with a radius based test area for a region growing mechanism is that, if it is required that only a majority of elements in the test area are within the tolerance range, then undesired elements may be included in the region or volume being grown, and narrow connections may even be crossed. If all elements within the test area must be within the tolerance range, then those issues may be avoided, but the region or volume may only grow to within the radius distance of the edge of the desired object in at least some places. This may result in an inset from the desired true edge of the object being selected; elements within this edge inset will not be included in the region or volume, even if the elements meet the test criteria.